local surjection property
On subdifferential chain rule of matrix factorization and beyond
Guan, Jiewen, So, Anthony Man-Cho
Strictly speaking, many existing "subgradient" algorithms for training deep neural networks (e.g., [1, 2]) are not necessarily subgradient-based in any conventional sense due to the possible failure of equality-type subdifferential chain rules for the underlying problems. Consequently, it is often difficult to establish rigorous theoretical guarantees for these algorithms. Therefore, it is meaningful to study conditions under which equality-type subdifferential chain rules hold for nonsmooth functions that arise in applications. Apart from this perspective, subdifferential chain rules are also helpful in some other tasks, e.g., stationarity testing [3] and landscape analysis [4]. Unfortunately, the research along this direction is still quite limited. In the recent work [5], an efficiently-verifiable necessary and sufficient data qualification for the validity of subdifferential chain rules in training two-layer ReLU neural networks is developed. Motivated by this, it is very natural to ask if we can further extend these theories to other more sophisticated neural networks, such as those carrying some multilinear structures (instead of the linearity underlying the ReLU neural networks), which are prevalent in recommender systems studies; see, e.g., [6, 7, 8, 9, 10, 11, 12, 13, 14]. However, due to the multilinear structure involved, the situation becomes drastically different from the linear setting; e.g., the Jacobian of any multilinear mapping at the origin is always zero, which prevents the application of the well-known surjectivity condition for subdifferential chain rules (see, e.g., [15, Exercise 10.7]). As a consequence, to achieve the goal, new techniques have to be developed.